|
|
|
| Propagation Source Tracing Algorithm Based on Priori Estimation |
| YU Huan1, ZHANG Sunxian1, LIU Ziang1, WANG Zhixiao1 |
| 1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116 |
|
|
|
|
Abstract The deficiencies of most existing spreading source detection methods are low detection rate and large error distance due to the disregard of priori estimation of source node. The infection model, susceptible-infected(SI), is utilized to simulate the propagation process of information in weighed social networks, and a spreading source tracing algorithm based on priori estimation is proposed. Both infected and uninfected nodes of neighborhood are considered, and priori estimations are assigned to the source node according to the number relationship between infected nodes and uninfected nodes. Experiments on artificial and real networks indicate that the proposed algorithm achieves a high detection rate, a small error distance and a high accuracy of real source node ranking.
|
|
Received: 10 June 2019
|
|
|
| Fund:Supported by National Natural Science Foundation of China(No.61876186,61976217) |
|
Corresponding Authors:
WANG Zhixiao, Ph.D., professor. His research interests include data mining and social network analysis.
|
| About author:: YU Huan, master student. His research interests include social network source detection.ZHANG Sunxian, master student. His research interests include network dismantling.LIU Ziang, master student. His research interests include social network analysis. |
|
|
|
[1] LIU Q, XIANG B, YUAN N J, et al. An Influence Propagation View of PageRank. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3). DOI: 10.1145/3046941.
[2] 黄春林,刘兴武,邓明华,等.复杂网络上疾病传播溯源算法综述.计算机学报, 2018, 41(6): 1376-1399.
(HUANG C L, LIU X W, DENG M H, et al. A Survey on Algorithms for Epidemic Source Identification on Complex Networks. Chinese Journal of Computers, 2018, 41(6): 1376-1399.)
[3] 郭 琛.社交网络分析与信息传播研究.硕士学位论文.上海:复旦大学, 2012.
(GUO C. Research on Social Network Analysis and Information Dissemination. Master Dissertation. Shanghai, China: Fudan University, 2012.)
[4] SHAH D, ZAMAN T. Rumors in a Network: Who′s the Culprit? IEEE Transactions on Information Theory, 2009, 57(8): 5163-5181.
[5] SHAH D, ZAMAN T. Detecting Sources of Computer Viruses in Net-works. ACM SIGMETRICS Performance Evaluation Review, 2010, 38(1): 203-214.
[6] ZHU K, YING L. Information Source Detection in the SIR Model: A Sample Path Based Approach. IEEE/ACM Transactions on Networking, 2016, 24(1): 408-421.
[7] LOKHOV A Y, MEZARD M, OHTA H, et al. Inferring the Origin of an Epidemic with a Dynamic Message-Passing Algorithm. Physical Review E, 2013, 90(1). DOI: 10.1103/PhysRevE.90.012801.
[8] ALTARELLI F, BRAUNSTEIN A, DALL′ASTA L, et al. Bayesian Inference of Epidemics on Networks via Belief Propagation. Physical Review Letters, 2013, 112(11): 118701-118706.
[9] LIM S, HAO J, LU Z X, et al. Approximating the k-Minimum Distance Rumor Source Detection in Online Social Networks // Proc of the 27th International Conference on Computer Communication and Networks. Washington, USA: IEEE, 2018. DOI:10.1109/ICCCN.2018.8487400.
[10] JIANG J J, WEN S, YU S, et al. Rumor Source Identification in Social Networks with Time-Varying Topology. IEEE Transactions on Dependable and Secure Computing, 2018, 15(1): 166-179.
[11] ZHOU Y S, WU C J, ZHU Q Y, et al. Rumor Source Detection in Networks Based on the SEIR Model. IEEE Access, 2019, 7: 45240-45258.
[12] PAN J C, ZHANG W Y. Identifying Rumor Source Using Dominant Eigenvalue of Nonbacktracking Matrix // Proc of the IEEE Global Conference on Signal and Information Processing. Washington, USA: IEEE, 2018, 748-752.
[13] CHANG B, CHEN E H, ZHU F D, et al. Maximum a Posteriori>Estimation for Information Source Detection. IEEE Transactions on Systems, Man, and Cybernetics(Systems), 2018. DOI: 10.1109/TSMC.2018.2811410.
[14] WATTS D J, STROGATZ S H. Collective Dynamics of ′Small-World′ Networks. Nature, 1998, 393: 440-442.
[15] LESKOVEC J, HHTTENLOCHER D, KLEINBERG J. Predicting Positive and Negative Links in Online Social Networks // Proc of the 19th International Conference on World Wide Web. New York, USA: ACM, 2010: 641-650.
[16] LESKOVEC J, KLEINIBER J, FALOUTSOS C. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1). DOI:10.1145/1217299.1217301.
[17] BARABÁSI A L, ALBERT R. Emergence of Scaling in Random Networks. Science, 1999, 286 (5439): 509-512
[18] NGUYEN D T, NGUYEN N P, THAI M T. Sources of Misinformation in Online Social Networks: Who to Suspect? // Proc of the IEEE Military Communications Conference. Washington, USA: IEEE, 2013. DOI .10.1109/MILCOM.2012.6415780. |
|
|
|
2020, Vol. 33 
